The present invention is directed to a communication network. More particularly, the present invention is directed to a source routing communication network of arbitrary topology that includes reduced header information.
Many types of digital communication networks exist that provide paths between nodes to communicate data or "messages." Some networks, generally referred to as circuit switched networks, provide a single, direct, point-to-point path between nodes. Other networks, generally referred to as packet-switched networks, provide multiple potential paths between nodes, and the route taken may vary frequently. Some packet-switched networks include routers between nodes. The routers, which typically include multiple input/output ports, receive incoming data on an input port and send the data on a selected output port.
FIG. 1 illustrates an embodiment of a packet-switched communication network 8 that includes routers 10-13 and nodes 31-38. Nodes 31-38 represent various hardware entities. For example, if communication network 8 represents a remote network, such as the Internet, each node 31-38 may be a computer server. If communication network 8 represents a multiprocessor computer system, each node 31-38 may be a processor, a peripheral device such as random access memory, or a disk drive. Nodes 31-38 are the source and destination of messages on communication network 8.
Each router 10-13 in communication network 8 includes a plurality of communication input/output ports which are coupled to communication paths. Routers 10-13 are coupled to each other via communication paths 20-25. For example, router 10 is coupled to router 11 via path 21 and to router 12 via path 22.
Each router 10-13 is coupled to at least one node 31-38 via communication paths 40-47, respectively. For example, node 34 is coupled to router 12 via communication path 43, and node 32 is coupled to router 13 via communication path 41.
Communication network 8 provides multiple routes between nodes 31-38. If, for example, node 31 must send a message to node 35, the message can travel along path 40, through router 13, along path 23, through router 11, along path 44 to node 35. In an alternative route, the message can travel along path 40, through router 13, along path 24, through router 12, along path 25, through router 11, along path 44 to node 35.
Communication network 8 has an arbitrary topology because the number and position of routers and nodes is not fixed.
Various routing schemes exist for routing a message from one node to another node in communication network 8. One such scheme is known as source routing. With source routing, the source node selects the route that the message travels to reach the destination node. The selected route is included in a header that is appended to the message. When the message arrives at a router, that router will select an output port for the message based on the header information.
Some messages sent on communication network 8 require a reply to the source node. For example, a source node might require an acknowledgment from the destination node that the message was received. In most known source routing schemes, the part of the header that specifies the route from the source node to the destination node is lost when the message arrives at the destination node. For example, with hop-count based mesh routing, the route is decremented at each hop so that it contains no information by the time it reaches the destination. With Myrinet routing, the route is stripped off entirely. Therefore, in these known source routing schemes, when a reply message is required, both the source node to destination node route and the source node address must be included in the header so that the destination node can determine the return route. Thus, the header includes redundant routing information. However, to support very small messages efficiently, it is desirable to limit the amount of information in the message header.
Hypercube routing is a known source routing scheme that allows the return route to be constructed from the source node to destination node route. However, the Hypercube routing scheme is limited to communication networks that implement a hypercube topology, which requires 2.sub.n nodes, where n&gt;0 and is an integer. This specific non-arbitrary topology limits the flexibility of the design of a communication network.
Based on the above, there is a need for a source routing communication network of arbitrary topology that utilizes a small message header which includes the source node to destination node route, and that allows a return route from the destination node to be constructed from the header.